package UnionFind;

/**
 * @author chetaifu
 * 第一版Union-Find本质就是一个数组
 */
public class UnionFind1 {
    private int[] id;

    private int size;

    public UnionFind1(int n){
        size = n;
        id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
    }

    /**
     * O(1)复杂度
     * */
    public int find(int p){
        assert (p >= 0 && p < size);
        return id[p];
    }

    /**
     * O(1)复杂度
     * */
    public boolean isConnected(int p, int q){
        return id[p] == id[q];
    }

    /**
     * O(n)复杂度
     * */
    public void unionElement(int p, int q){
        int pId = find(p);
        int qId = find(q);

        if(pId == qId) return;

        for (int i = 0; i < size; i++) {
            if(id[i] == qId){
                id[i] = pId;
            }
        }
    }

}
